package com.cqs.leetcode.string;

import com.google.common.collect.Lists;

import java.util.*;

/**
 * xw
 * 2022/10/22
 */
public class TextJustification68 {


    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            int remain = maxWidth;
            final int start = i;
            while (i < words.length && remain >= words[i].length()) {
                remain -= words[i++].length() + 1;
            }
            i--;
            StringBuilder line = new StringBuilder(maxWidth);
            if (i == words.length - 1) {
                for (int j = start; j < words.length - 1; j++) {
                    line.append(words[j]);
                    line.append(" ");
                }
                line.append(words[i]);
                for (int j = line.length(); j < maxWidth; j++) {
                    line.append(" ");
                }
                result.add(line.toString());
                break;
            }
            int spaces = remain + i - start + 1;
            //单词平均有多少个空格
            int space = i == start ? spaces : spaces / (i - start);
            StringBuilder base = new StringBuilder(space);
            for (int j = 0; j < space; j++) {
                base.append(" ");
            }
            int delta = i == start ? spaces : spaces % (i - start);
            for (int j = start; j < i; j++) {
                line.append(words[j]);
                line.append(base);
                if (delta > 0) {
                    line.append(" ");
                    --delta;
                }
            }
            line.append(words[i]);
            for (int j = line.length(); j < maxWidth; j++) {
                line.append(" ");
            }
            result.add(line.toString());
        }
        return result;
    }

    public static void main(String[] args) {

        Map<String[], Integer> cases = new LinkedHashMap<>();
        cases.put(new String[]{"This", "is", "an", "example", "of", "text", "justification."},16);
        cases.put(new String[]{"Science", "is", "what", "we", "understand", "well", "enough", "to", "explain", "to", "a", "computer.", "Art", "is", "everything", "else", "we", "do"}, 20);
        TextJustification68 t = new TextJustification68();
        for (String[] key : cases.keySet()) {
            List<String> result = t.fullJustify(key, cases.get(key));
            System.out.println(Lists.newArrayList(key));
            for (String s : result) {
                System.out.println(s);
            }

        }

    }

}
